<html>
<head><title>flipcode - Quake 2 BSP File Format</title>
<style type="text/css">


a.menulink:link    {color: #b9ffd0; }
a.menulink:visited {color: #b9ffd0; }
a.menulink:active  {color: #b9ffd0; }

a.menulinkempty:link    {color: #b9ffd0; }
a.menulinkempty:visited {color: #b9ffd0; }
a.menulinkempty:active  {color: #b9ffd0; }
a.menulinkempty:link, a.menulinkempty:visited, a.menulinkempty:active {text-decoration: none}

a.orangelink:link    { color:#FFAB04; }
a.orangelink:visited { color:#FFAB04; }
a.orangelink:active  { color:#FFAB04; }

a.palegreen:link    {color: #b9ffd0; }
a.palegreen:visited {color: #b9ffd0; }
a.palegreen:active  {color: #b9ffd0; }

a.bluelink:link    { color:#03F0FF; }
a.bluelink:visited { color:#03F0FF; }
a.bluelink:active  { color:#03F0FF; }

a.softyellow:link     { color:#FFFCA9; }
a.softyellow:visited  { color:#FFFCA9; }
a.softyellow:active   { color:#FFFCA9; }

a.nounderline:link        {color: #FFFCA9; }
a.nounderline:visited     {color: #FFFCA9; }
a.nounderline:active      {color: #FFFCA9; }
a.nounderline:link, a.nounderline:visited, a.nounderline:active {text-decoration: none}

<!--
#code_comment { font-family:Courier,Courier New; font-size:12px; color:#007f00; }
#code_text    { font-family:Courier,Courier New; font-size:12px; color:#000000; }
#code_keyword { font-family:Courier,Courier New; font-size:12px; color:#0000FF; }
-->

</style>
</head>
<body bgcolor="#000000" text="#ffffff" link="#FFFCA9" vlink="#FFFCA9" alink="#FFFCA9">
<center>
<script type="text/javascript"><!--
google_ad_client = "pub-3512250068614659";
//728x90, created 1/8/08
google_ad_slot = "8394943283";
google_ad_width = 728;
google_ad_height = 90;
//--></script>
<script type="text/javascript"
src="http://pagead2.googlesyndication.com/pagead/show_ads.js">
</script>
<br>

<br><center><table cellspacing=0 cellpadding=2 border=0 width="80%"><tr><td background="comments_bar2.jpg" bgcolor="#333333" width="100" valign="center"><font size=1>&nbsp;</font></td></tr></table></center><br>
<center>
<table width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td>
<font size=3 face="Verdana, Helvetica" color="#ffffff"><b>Quake 2 BSP File Format</b><br>
<font size=2>by <!--GO AWAY SPAM!!!--><script language="javascript">document.write('<a href=\"mailto:' +  '' + '' + ''    
+''    
+''    
+ 'amcguire' + ''    
+''    
+''    
+''    
+''    
+''    
+''    
+ '@' + 'andrew' + ''    
+''    
+''    
+ '.' + ''    
+''    
+''    
+''    
+''    
+''    
+''    
+''    
+ 'cmu.edu\">' + 'Max McGuire' + '</a>')</script> (07 June 2000)</font>
</font>
<br><br><br>
</td>
<td align="right" valign="top"><font face="Verdana, Helvetica" size=2><a href="articles.shtml">Return to The Archives</a>
</td>
</tr></table>
</center><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Introduction
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The purpose of this document is to detail the structure of the BSP file format
used by Quake 2 to store maps; in particular, the focus is on rendering Quake 2
worlds.  Although there is other information contained in the BSP file used for
other game elements (such as enemy AI, etc.), I don't have complete information
on them so I won't discuss these beyond mentioning them. If you have anything to
contribute on these parts please feel free to e-mail at the address listed
above.  Also, although I've tried my best to minimize errors, if you find
anything that is incorrect please let me know.<br><br>In addition to just a bare description of the BSP file format, this document
also attempts explain the techniques which are at the core of the Quake
rendering engine.  In general it's assumed that the reader is familiar with the
basic principles of 3D graphics, including the BSP tree data structure.<br><br>This document covers version 38 of the BSP file format which is the version used
by Quake 2. This is also the version of the BSP file format used by Kingpin
(which was created using the Quake 2 engine) and therefore all of the
information contained is relevant to those files as well.  While Quake 1 and
Quake 3: Arena use similar BSP formats the formats are not directly compatible. 
However, because of the similarity in the structure and techniques, this
document should be of some use to anyone interested in these formats as well.<br><br>My information about the Quake 2 BSP format was all learned by a lot of
experimentation in implementing my own Quake 2 BSP renderer along with examining
source code for Quake-like engines generously released into the public domain by
their authors. These engines were the Twister Engine by Stefano Lanza, the
Arnfold 2 Engine by Andrei Fortuna and the Poly Engine by Alexey Goloshubin. The
source code for all three of these engines is freely available on the web; if
you find something's missing out of this document, I recommend you check out
these engines.  Id Software has also released the source code for their Quake 2
tools, including the QBSP map file compiler which outputs BSP files, although I
didn't find it to be particularly useful in my own exploration.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Legality
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Using id Software file formats in a publicly distributed application always
seemed a little questionable to me in terms of legality.  In preparation of this
document I contacted id Software to resolve the issue; John Carmack was kind
enough to send along this response:<br><br>"We do not legally protect the file formats, but you can't use any of the
released tools, or tools derived from them (except the GPL'd Quake 1 tools) to
generate content for a commercial venture. If you are writing everything
yourself, no problem."</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Conventions
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

To help make this document easier to read I've included C-syntax structures for
all of the file structures (with the assumption that there no extra padding
bytes between the fields).  To simplify the notation and standardize the
meaning, the abbreviations int32 and uint32 are used for signed and unsigned
32-bit integers; similar abbreviations are used for 16-bit and 8-bit integers as
well.  Also, the following two structures are used throughout the BSP file
format to store vertices and vectors:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> point3f
{<br><br>    <font color="#0000ff">float</font> x;
    <font color="#0000ff">float</font> y;
    <font color="#0000ff">float</font> z;<br><br>};<br><br><font color="#0000ff">struct</font> point3s
{<br><br>    int16 x;
    int16 y;
    int16 z;<br><br>};
 </font></pre></td></tr></table></div></center><br><br>The second version is used in some places to conserve memory where the precision
is unessential (like storing the bounding boxes) since it takes only 6 bytes
compared with the 12 byte floating point version.  These are regular integer
representations, not fixed-point.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Rendering
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

To give an introduction to the terminology used and the idea behind some of the
data structures, this section briefly describes the process of rendering a Quake
2 environment.<br><br>A Quake map is carved up into convex regions that become the leaves of the BSP
tree, and anytime the camera is positioned within a level it is contained in
exactly one of these convex regions.  The leaves are grouped together with
neighboring leaves to form clusters; exactly how these clusters are formed is
determined by the tool that creates the BSP file.  For each cluster, a list of
all of the other clusters which are potentially visible is stored.  This is
referred to as the potentially visible set (PVS).<br><br>To render a Quake map, first the BSP tree is traversed to determine which leaf
the camera is located in.  Once we know which leaf the camera is in, we know
which cluster it's in (remembering that each leaf is contained in exactly one
cluster).  The PVS for the cluster is then decompressed giving a list of all the
potentially visible clusters from the camera location.  Leaves store a bounding
box which his used to quickly cull leaves that are not within the viewing
frustum.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

BSP Tree
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Many people incorrectly associate the BSP tree with the visibility algorithm
used by Quake and similar engines.  As described above, the visible surface
determination is done using a precomputed PVS.  The BSP tree is primarily used
to divide the map into regions and to quickly determine which region the camera
is in.  As a result, it isn't that fundamental to any of the rendering
algorithms used in Quake and  any data structure giving a spatial subdivision
(like an octree or a k-D tree) could be used instead.  BSP trees are very simple
however, and they are useful for some of the other non-rendering tasks in the
Quake engine.<br><br>Traditionally when discussing BSP trees a distinction is made between those BSP
trees that store the faces in the leaves (leaf-based BSP trees) and those that
store them in the internal nodes (node-based BSP trees).  The variation of BSP
tree Quake uses is actually both; the reason for this is the dual use of the BSP
tree in both rendering and in collision detection.  For the purpose of
rendering, it is useful to have the faces stored in the leaves because of the
way the PVS is used.  If you're not interested in performing collision
detection, the faces in the nodes can be completely ignored.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

File Header
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

As far as I know all BSP files are stored in a little-endian (Intel) byte order
and converted as loaded when used on a big-ending platform.  This allows the
same map files to be shared by Quake clients running on all different platforms. 
If you're going to be loading BSP files on a big-endian machine -- like a
Macintosh or UNIX machine -- you're going to have to be careful about swapping
the byte order.<br><br>The Quake BSP file format is organized around a directory structure, where all
of the data is contained in "free floating" lumps within the file.  There's a
directory in the beginning of the file which tells the offset of the start of
the lump and the length.  This directory comes after the first 8 bytes of the
file is a table of contents which gives the location and length of these lumps.<br><br>The format for the BSP file header is the bsp_header structure shown below:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_lump
{<br><br>    uint32    offset;     <font color="#007f00">// offset (in bytes) of the data from the beginning of the file
</font>    uint32    length;     <font color="#007f00">// length (in bytes) of the data
</font>
};<br><br><font color="#0000ff">struct</font> bsp_header
{<br><br>    uint32    magic;      <font color="#007f00">// magic number ("IBSP")
</font>    uint32    version;    <font color="#007f00">// version of the BSP format (38)
</font>
    bsp_lump  lump[19];   <font color="#007f00">// directory of the lumps
</font>
};
 </font></pre></td></tr></table></div></center><br><br>The first four bytes of the BSP file is a tag which can be used to identify the
file as an id Software BSP file. These bytes spell out "IBSP".  Following that
is a 32-bit unsigned integer specifying the version number.  As mentioned
earlier, the version described in this document is 38 (decimal).<br><br>Below is a table showing the different lumps contained in the BSP file and their
index in the lump array in the header. The purpose of lumps marked with a
question mark is not known (the names are derived from the QBSP source code),
however they are not needed for constructing a simple Quake level renderer.<br><br><pre>
	Index	Name                    Description
	0	Entities                MAP entity text buffer	
	1	Planes                  Plane array	
	2	Vertices                Vertex array	
	3	Visibility              Compressed PVS data and directory for all clusters	
	4	Nodes                   Internal node array for the BSP tree	
	5	Texture Information     Face texture application array	
	6	Faces                   Face array	
	7	Lightmaps               Lightmaps	
	8	Leaves                  Internal leaf array of the BSP tree	
	9	Leaf Face Table         Index lookup table for referencing the face array from a leaf	
	10	Leaf Brush Table        ?	
	11	Edges                   Edge array	
	12	Face Edge Table         Index lookup table for referencing the edge array from a face	
	13	Models                  ?	
	14	Brushes                 ?	
	15	Brush Sides             ?	
	16	Pop                     ?	
	17	Areas                   ?       	
	18	Area Portals            ?
</pre>
Most of the lumps are stored as an array of structures where the structure has a
fixed size.  For instance the vertex lump is an array of point3f structures. 
Since each point3f is 12 bytes, the number of vertices can be computed by
dividing the size of the vertex lump by 12.  Similar computations can be done
for the plane, node, texture information, faces, leaf and edge lumps.<br><br>In the following sections, the purpose and structure of the known lumps is
discussed.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Vertex Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The vertex lump is a list of all of the vertices in the world.  Each vertex is 3
floats which makes 12 bytes per vertex.  You can compute the numbers of vertices
by dividing the length of the vertex lump by 12. <br><br>Quake uses a coordinate system in which the z-axis is pointing in the "up"
direction.  Keep in mind that if you modify the coordinates to use a different
system, you will also need to adjust the bounding boxes and the plane equations.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Edge Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Not only are vertices shared between faces, but edges are as well.  Each edge is
stored as a pair of indices into the vertex array.  The storage is two 16-bit
integers, so the number of edges in the edge array is the size of the edge lump
divided by 4.  There is a little complexity here because an edge could be shared
by two faces with different windings, and therefore there is no particular
"direction" for an edge.  This is further discussed in the section on face
edges.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Face Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The face lump stores an array of bsp_face structures which have the following
format:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_face
{<br><br>    uint16   plane;             <font color="#007f00">// index of the plane the face is parallel to
</font>    uint16   plane_side;        <font color="#007f00">// set if the normal is parallel to the plane normal
</font>
    uint32   first_edge;        <font color="#007f00">// index of the first edge (in the face edge array)
</font>    uint16   num_edges;         <font color="#007f00">// number of consecutive edges (in the face edge array)
</font>	
    uint16   texture_info;      <font color="#007f00">// index of the texture info structure	
</font>   
    uint8    lightmap_syles[4]; <font color="#007f00">// styles (bit flags) for the lightmaps
</font>    uint32   lightmap_offset;   <font color="#007f00">// offset of the lightmap (in bytes) in the lightmap lump
</font>
};
 </font></pre></td></tr></table></div></center><br><br>The size of the bsp_face structure is 20 bytes, the number of faces can be
determined by dividing the size of the face lump by 20.<br><br>The plane_side is used to determine whether the normal for the face points in
the same direction or opposite the plane's normal.  This is necessary since
coplanar faces which share the same node in the BSP tree also share the same
normal, however the true normal for the faces could be different.  If plane_side
is non-zero, then the face normal points in the opposite direction as the
plane's normal.<br><br>The details of texture and lightmap coordinate generation are discussed in the
section on texture information and lightmap sections.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Face Edge Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Instead of directly accessing the edge array, faces contain indices into the
face edge array which are in turn used as indices into the edge array.  The face
edge lump is simply an array of unsigned 32-bit integers.  The number of
elements in the face edge array is the size of the face edge lump divided by 4
(note that this is not necessarily the same as the number of edges).<br><br>Since edges are referenced from multiple sources they don't have any particular
direction.  If the edge index is positive, then the first point of the edge is
the start of the edge; if it's negative, then the second point is used as the
start of the edge (and obviously when you look it up in the edge array you drop
the negative sign).</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Plane Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The plane lump stores and array of bsp_plane structures which are used as the
splitting planes in the BSP. The format for for the bsp_plane structure is:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_plane
{<br><br>    point3f   normal;      <font color="#007f00">// A, B, C components of the plane equation
</font>    <font color="#0000ff">float</font>     distance;    <font color="#007f00">// D component of the plane equation
</font>    uint32    type;        <font color="#007f00">// ?
</font>
};
 </font></pre></td></tr></table></div></center><br><br>Each bsp_plane structure is 20 bytes, so the number of planes is the size of the
plane lump divided by 20.<br><br>The x, y and z components of the normal correspond to A, B, C constants and the
distance to the D constant in the  plane equation:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
F(x, y, z) = Ax + By + Cz - D
 </font></pre></td></tr></table></div></center><br><br>A point is on the plane is F(x, y, z) = 0, in front of the plane if F(x, y, z) >
0 and behind the plane if  F(x, y, z) < 0.  This is used in the traversal of the
BSP tree is traversed.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Node Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The nodes are stored as an array in the node lump, where the first element is
the root of the BSP tree.  The format of a node is the bsp_node structure:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_node
{<br><br>    uint32   plane;             <font color="#007f00">// index of the splitting plane (in the plane array)
</font>    
    int32    front_child;       <font color="#007f00">// index of the front child node or leaf
</font>    int32    back_child;        <font color="#007f00">// index of the back child node or leaf
</font>   
    point3s  bbox_min;          <font color="#007f00">// minimum x, y and z of the bounding box
</font>    point3s  bbox_max;          <font color="#007f00">// maximum x, y and z of the bounding box
</font>	
    uint16   first_face;        <font color="#007f00">// index of the first face (in the face array)
</font>    uint16   num_faces;         <font color="#007f00">// number of consecutive edges (in the face array)
</font>
};
 </font></pre></td></tr></table></div></center><br><br>Each bsp_node is 28 bytes, so the number of nodes is the size of the node lump
divided by 28.<br><br>Since a child of a node may be a leaf and not a node, negative values for the
index are used to incate a leaf.  The exact position in the leaf array for a
negative index is computed as -(index + 1) so that the first negative number
maps to 0.<br><br>Since the bounding boxes are axis aligned, the eight coordinates of the box can
be found from the minimum and maximum coordinates stored in the bbox_min and
bbox_max fields.<br><br>As mentioned earlier, the faces listed in the node are not used for rendering
but rather for collision detection.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Leaf Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The leaf lump stores an array of bsp_leaf structures which are the leaves of the
BSP tree.  The format of the bsp_leaf structure is:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_leaf
{
   
    uint32   brush_or;          <font color="#007f00">// ?
</font>	
    uint16   cluster;           <font color="#007f00">// -1 for cluster indicates no visibility information
</font>    uint16   area;              <font color="#007f00">// ?
</font>
    point3s  bbox_min;          <font color="#007f00">// bounding box minimums
</font>    point3s  bbox_max;          <font color="#007f00">// bounding box maximums
</font>
    uint16   first_leaf_face;   <font color="#007f00">// index of the first face (in the face leaf array)
</font>    uint16   num_leaf_faces;    <font color="#007f00">// number of consecutive edges (in the face leaf array)
</font>
    uint16   first_leaf_brush;  <font color="#007f00">// ?
</font>    uint16   num_leaf_brushes;  <font color="#007f00">// ?
</font>
};
 </font></pre></td></tr></table></div></center><br><br>The bsp_leaf structure is 28 bytes so the number of leaves is the size of the
leaf lump divided by 28.<br><br>Leaves are grouped into clusters for the purpose of storing the PVS, and the
cluster field gives the index into the array stored in the visibility lump.  See
the Visibility section for more information on this.  If the cluster is -1, then
the leaf has no visibility information (in this case the leaf is not a place
that is reachable by the player).</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Leaf Face Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Instead of directly accessing the face array, leaves contain indices into the
leaf face array which are in turn used as indices into the face array.  The face
edge lump is simply an array of unsigned 16-bit integers.  The number of
elements in this array is the size of the leaf face lump divided by 2; this is
not necessarily the same as the number of faces in the world.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Texture Information Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Texture information structures specify all of the details about how a face is
textured.  The structure of the a single texture information is the bsp_texinfo
structure:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_texinfo
{<br><br>    point3f  u_axis;
    <font color="#0000ff">float</font>    u_offset;
   
    point3f  v_axis;
    <font color="#0000ff">float</font>    v_offset;<br><br>    uint32   flags;
    uint32   value;<br><br>    <font color="#0000ff">char</font>     texture_name[32];<br><br>    uint32   next_texinfo;<br><br>};
 </font></pre></td></tr></table></div></center><br><br>The bsp_texinfo structure is 76 bytes, so the number of texture information
structures is the size of the lump divided by 76.<br><br>Textures are applied to faces using a planar texture mapping scheme.  Instead of
specifying texture coordinates for each of the vertices of the face, two texture
axes are specified which define a plane.  Texture coordinates are generated by
projecting the vertices of the face onto this plane.<br><br>While this may seem to add some complexity to the task of the programmer, it
greatly reduces the burden of the level designer in aligning textures across
multiple faces.<br><br>The texture coordinates (u, v) for a point(x, y, z) are found using the
following computation:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
u = x * u_axis.x + y * u_axis.y + z * u_axis.z + u_offset
v = x * v_axis.x + y * v_axis.y + z * v_axis.z + v_offset
 </font></pre></td></tr></table></div></center><br><br>My own experience has shown that it is perfectly reasonable to generate the
coordinates in real-time rather than storing them.<br><br>The texture name is stored with a path but without any extension.  Typically, if
you are loading a Quake 2 map you would append the extension "wal" to the name
and then load it from the PAK file.  If you're loading a Kingpin map you would
append the extension "tga" and then load if from disk (Kingpin stires the
textures outside of the PAK file).  See the section on the WAL texture format
for more details.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Visibility Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Leaves are grouped into clusters for the purpose of storing the visibility
information.  This is to conserve space in the PVS since it's likely that nearby
leaves will have similar potentially visible areas.  The first 4 bytes of the
visibility lump is a 32-bit unsigned integer indicating the number of clusters
in the map, and after that is an array of bsp_vis_offset structures with the
same number of elements as there are clusters.  The bsp_vis_offset structure
format is:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> bsp_vis_offset
{<br><br>	uint32 pvs;   <font color="#007f00">// offset (in bytes) from the beginning of the visibility lump
</font>	uint32 phs;   <font color="#007f00">// ?
</font>
};
 </font></pre></td></tr></table></div></center><br><br>The rest of the visibility lump is the actual visibility information.  For every
cluster the visibility state (either visible or occluded) is stored for every
other cluster in the world.  Clusters are always visible from within themselves. 
Because this is such a  massive amount of data, this array is stored as a bit
vector (one bit per element) and 0's are run-length-encoded. Here's an example
of a C-routine to decompress the PVS into a byte array (this was adapted from
the "Quake Specifications" document):<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">int</font> v = offset;<br><br>memset(cluster_visible, 0, num_clusters);<br><br><font color="#0000ff">for</font> (<font color="#0000ff">int</font> c = 0; c &lt; num_clusters; v++) {
 
   <font color="#0000ff">if</font> (pvs_buffer[v] == 0) {
      v++;     
      c += 8 * pvs_buffer[v];
   } <font color="#0000ff">else</font> {
      <font color="#0000ff">for</font> (uint8 bit = 1; bit != 0; bit *= 2, c++) {
         <font color="#0000ff">if</font> (pvs_buffer[v] & bit) {
            cluster_visible[c] = 1;
         }
      }
   }   <br><br>}
 </font></pre></td></tr></table></div></center></font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Lightmap Lump
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Static lighting is handled in the Quake environment using lightmaps, which are
low resolution bitmaps that are combined with the texture when rendering a face. 
Lightmaps are unique to a face (unlike textures which may be used on multiple
faces).  The maximum size for any lightmap is 16x16 which is enforced by the BSP
creation tool by splitting faces which would require larger lightmaps.  In Quake
1 lightmaps were limited to grayscale, however Quake 2 allows for 24-bit true
color lighting.<br><br>Lightmaps are applied either through multi-texturing or multi-pass rendering and
should be multiplied with the texture for a face when rendering.<br><br>The lightmap lump contains the data for all of the lightmaps in the world stored
consecutively.  Faces store the offset of their lightmap in this lump in the
bsp_face structure's lightmap_offset. The actual lightmap data is stored in a
24-bits-per-pixel RGB format in a left-right, top-down order starting at this
offset.<br><br>The width and height of a lightmap isn't explicitly stored anywhere and must be
computed. If max_u is the maximum u component of all of the texture coordinates
for a face, and min_u is the minimum u component of all the texture coordinates
for a face (and similarly for the max_v and min_v), then the width and height of
the lightmap for the face is given by the computation:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
lightmap_width  = ceil(max_u / 16) - floor(min_u / 16) + 1
lightmap_height = ceil(max_v / 16) - floor(min_v / 16) + 1
 </font></pre></td></tr></table></div></center><br><br>For information on computing the texture coordinates for a face see the Texture
Information Lump section.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

WAL Image Format
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

Quake 2 stores textures in a proprietary 2D image format called WAL.  While this
isn't actually part of the BSP file format, it's essential information for
loading Quake 2 maps so I've decided to include it.  Note that this doesn't
apply to Kingpin maps which use textures stored as TGA files.<br><br>WAL textures are stored in a 8-bit indexed color format with a specific palette
being used by all textures (this palette is stored in the PAK data file that
comes with Quake 2).  Four mip-map levels are stored for each texture at sizes
decreasing by a factor of two.  This is mostly for software rendering since most
3D APIs will automatically generate the mip-map levels when you create a
texture.  Each frame of an animated texture is stored as an individual WAL file,
and the animation sequence is encoded by storing the name of the next texture in
the sequence for each frame; texture names are stored with paths and without any
extension.<br><br>The format for the WAL file header is the wal_header structure:<br><br><center><div style="width:100%; overflow:auto; background-color:#FFFFFF; border:solid 1px #c0c0c0;"><table width="100%" bgcolor="#ffffff" cellspacing=0 cellpadding=12 border=0><tr><td width="100%" bgcolor="#ffffff"><pre><font face="Courier, Courier New" color="#000000">
<font color="#0000ff">struct</font> wal_header
{<br><br>    <font color="#0000ff">char</font>    name[32];        <font color="#007f00">// name of the texture
</font> 
    uint32  width;           <font color="#007f00">// width (in pixels) of the largest mipmap level
</font>    uint32  height;          <font color="#007f00">// height (in pixels) of the largest mipmap level
</font> 
    int32   offset[4];       <font color="#007f00">// byte offset of the start of each of the 4 mipmap levels
</font>
    <font color="#0000ff">char</font>    next_name[32];   <font color="#007f00">// name of the next texture in the animation
</font>
    uint32  flags;           <font color="#007f00">// ?
</font>    uint32  contents;        <font color="#007f00">// ?
</font>    uint32  value;           <font color="#007f00">// ?
</font>
};
 </font></pre></td></tr></table></div></center><br><br>The actual texture data is stored in an 8-bits-per-pixel raw format in a
left-right, top-down order.</font></td></tr></table>
</center><br><br><center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=3 color="#ffffff" face="Verdana, Helvetica, Arial, Times New Roman"><b>

Entities
<font size=1><br><img src="line_grey.png"><br><br></font></b></font></td></tr></table>
</center>
<center>
<table style="table-layout:fixed;" width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td width="100%">
<font size=2 color="#FFE291" face="Verdana, Helvetica, Arial, Times New Roman">

The entity section of the BSP file is an ASCII text buffer, formatted in the
same manner as the entities in the MAP file (recall that BSP files are compiled
from MAP files).  Entities are things like the player spawn points, lights,
health, ammunition and guns.  A comprehensive list of the entities used in Quake
1 (and because of the considerable overlap, Quake 2) is available in the MAP
file format section of the "Quake Specifications" document.</font></td></tr></table>
</center><center>
<table width="80%" cellspacing=0 cellpadding=0 border=0>
<tr>
<td>
<font size=2 face="Verdana" color="#ffffff">
<br>


</font>
</td>
</tr>
</table>
</center>
<center><table cellspacing=0 cellpadding=2 border=0 width="80%"><tr><td background="comments_bar2.jpg" bgcolor="#333333" width="100" valign="center"><font size=1>&nbsp;</font></td></tr></table></center><br>
<center><font face="Arial, Helvetica" size=1><font face="Helvetica,Tahoma,Verdana" size=1>Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s).  All rights reserved.</font> <center><font face="Helvetica,Tahoma,Verdana" size=1>Please read our <a href="terms.shtml">Terms</a>, <a href="terms.shtml">Conditions</a>, and <a href="terms.shtml">Privacy information</a>.</font></center></font></center>
<br>
</body>
</html>

